|
Chris Pollett >
Old Classes
> |
CS156 Spring 2004Practice Midterm 1To study for the midterm I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice midterm is below. Here are some facts about the actual midterm: (a) The midterm will be in class . (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (f) One problem (less typos) on the actual test will be from the practice test. 1. Consider the variation of the 8-puzzle where rather than having the number 1 through 8, we instead have two red tiles, three white tiles, and three blue tiles. The task in this variant is to arrange the two red tiles to the right at the top, then the next row in white and the last row in blue. Formally express this puzzle as a problem that might be solved by a problem solving agent. 2. For each of the following uninformed search strategies say whether or not it is complete. If it is not, give a counter-example situation: breadth first search, depth-first seach, depth-limited search. 3. Suppose uniform cost search was being used with a step size of 2 on the following weighted graph. a---4-->b |\ 3 \ | 2 V V c<-1-d Explain how the nodes would be expanded (starting from root a). 4. Suppose Manhattan distance was being used. Explain which would be the first four board considered after the initial board 5 X 2 1 4 8 6 7 3 using the A* algorithm. Give your reasoning. 5. Explain briefly the simulated annealing algorithm. 6. Suppose we are using an inductive learning approaches to learn a heuristic function for the A* algorithm. We have two feature f1 and f2 we are considering. Our training set consists of n1, for which f1(n1)=10 f2(n1)=7 and the value of the exact solution is 15 and n2, for which f1(n2)=7 f2(n2)=10 and the value of the exact solution is 20. What are the values of the constants c1 and c2 that we will learn? 7. Give an example where one can do an alpha prune and an example of where one can do a beta prune while doing minimax. Explain why your example works. 8. Consider the following situation for four light switches on the control panel of a nuclear power plant: (a) The leftmost two can never be both on. (b) At most three light can ever be on. Express this as a propositional logic knowledge base. 9. Give examples of situations of where hill-climbing algorithms can get stuck. 10. Explain how the SMA* and IDA* algorithms work. |